package leetcode_21_40;

import java.util.HashMap;
import java.util.Map;

public class isValidSudoku_36 {
    /**
     * 9 x 9 的数独是否有效
     * 数字 1-9 在每一行只能出现一次。
     * 数字 1-9 在每一列只能出现一次。
     * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
     *
     *暴力方法
     * 对三个条件分别判断、
     * 太慢了
     * 4ms
     * @param board
     * @return
     */
    public static boolean isValidSudoku(char[][] board) {
        Map<Integer,Integer> map1=new HashMap<>();         //记录九宫格各个数字的个数
        Map<Integer,Integer> map2=new HashMap<>();         //记录每一行各个数字的个数
        Map<Integer,Integer> map3=new HashMap<>();         //记录每一列各个数字的个数
        int count=0;
        for(int i=1;i<=9;i++){
             map1.put(i,0);
        }
        // 数字 1-9 在每一行只能出现一次。
        for(int i=0;i<9;i++ ){
            for(int t=1;t<=9;t++)
                map2.put(t,0);
            for(int t=0;t<9;t++){
                if(board[i][t]=='.')
                    continue;
                int num=board[i][t]-'0',a=map2.get(num);
                if( a==0){
                    map2.put(num,1);
                }
                else                        //数量不为0，即不满足条件
                    return false;
            }
        }
        // 数字 1-9 在每一列只能出现一次。
        for(int i=0;i<9;i++ ){
            for(int t=1;t<=9;t++)
                map3.put(t,0);
            for(int t=0;t<9;t++){
                if(board[t][i]=='.')
                    continue;
                int num= board[t][i]-'0', a=map3.get(num);
                if( a==0){
                    map3.put(num,1);
                }
                else                        //数量不为0，即不满足条件
                    return false;
            }
        }
        // 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
        for(int i=0,j=0;i<9&&j<9;){
            count++;
            //九宫格的数字填入map
            if(board[i][j]!='.') {
                int num = board[i][j] - '0', a = map1.get(num);
                if (a == 0) {
                    map1.put(num, 1);
                } else                        //数量不为0，即不满足条件
                    return false;
            }
            if( j==8 && ( i==2 || i==5)) {                   //一排三个九宫格遍历完
                count=0;
                j=0;
                i++;       //下一行，回第一列
                for(int t=1;t<=9;t++)
                    map1.put(t,0);
            }else if( count==9) {                               //遍历完一个九宫格
                count=0;
                i-=2;
                j++;      //回退两行，下一列
                for(int t=1;t<=9;t++)
                    map1.put(t,0);
            } else if(j==5 || j == 2 || j==8) {                          //遍历完一个九宫格的一行
                j-=2;
                i++;     //倒退两列，下一行
            }else {                                        //非特殊位置，下一列即可
                j++;
            }
        }
        return true;
    }

    /**
     * 高解
     * 与我最开始的想法一样，一次遍历，但是具体实施上我出现问题
     * 我对于界定此时3*3格子的位置判断没能把握好
     * @param board
     * @return
     */
    public static boolean isValidSudoku2(char[][] board) {
        int[][] rows = new int[9][9];        //1-9 在每一行
        int[][] columns = new int[9][9];  //1-9 在每一列
        int[][][] subboxes = new int[3][3][9];//1-9 在每一个3x3 宫内
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int index = c - '0' - 1;  //转为数字
                    rows[i][index]++;
                    columns[j][index]++;
                    subboxes[i / 3][j / 3][index]++;   //i /3 j/3   表示此时是哪里的3*3格子  ，最核心操作
                    if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
